<!DOCTYPE html>












  


<html class="theme-next pisces use-motion" lang="zh-Hans">
<head><meta name="generator" content="Hexo 3.8.0">
  <!-- hexo-inject:begin --><!-- hexo-inject:end --><meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">


  
  
  <link rel="stylesheet" href="/xieyuanhui/lib/needsharebutton/needsharebutton.css">

















  
  
  <link rel="stylesheet" href="/xieyuanhui/lib/fancybox/source/jquery.fancybox.css">







<link rel="stylesheet" href="/xieyuanhui/lib/font-awesome/css/font-awesome.min.css?v=4.6.2">

<link rel="stylesheet" href="/xieyuanhui/css/main.css?v=7.1.0">


  <link rel="apple-touch-icon" sizes="180x180" href="/xieyuanhui/images/apple-touch-icon-next.png?v=7.1.0">


  <link rel="icon" type="image/png" sizes="32x32" href="/xieyuanhui/images/favicon-32x32-next.png?v=7.1.0">


  <link rel="icon" type="image/png" sizes="16x16" href="/xieyuanhui/images/favicon-16x16-next.png?v=7.1.0">


  <link rel="mask-icon" href="/xieyuanhui/images/logo.svg?v=7.1.0" color="#222">


  <link rel="manifest" href="/xieyuanhui/images/manifest.json">


  <meta name="msapplication-config" content="/xieyuanhui/images/browserconfig.xml">





<script id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/xieyuanhui/',
    scheme: 'Pisces',
    version: '7.1.0',
    sidebar: {"position":"left","display":"post","offset":12,"onmobile":false,"dimmer":false},
    back2top: true,
    back2top_sidebar: false,
    fancybox: true,
    fastclick: false,
    lazyload: false,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>


  




  <meta name="description" content="原文地址：搞定操作系统面试，看这篇就够了（一） - Android 2012的文章 - 知乎https://zhuanlan.zhihu.com/p/62219376 概述基本特征并发并发是指宏观上在一段时间内能同时运行多个程序，而并行则指同一时刻能运行多个指令。 并行需要硬件支持，如多流水线、多核处理器或者分布式计算系统。 操作系统通过引入进程和线程，使得程序能够并发运行。 共享共享是指系统中的">
<meta name="keywords" content="操作系统">
<meta property="og:type" content="article">
<meta property="og:title" content="操作系统知识点">
<meta property="og:url" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/index.html">
<meta property="og:site_name" content="xieyuanhui的笔记">
<meta property="og:description" content="原文地址：搞定操作系统面试，看这篇就够了（一） - Android 2012的文章 - 知乎https://zhuanlan.zhihu.com/p/62219376 概述基本特征并发并发是指宏观上在一段时间内能同时运行多个程序，而并行则指同一时刻能运行多个指令。 并行需要硬件支持，如多流水线、多核处理器或者分布式计算系统。 操作系统通过引入进程和线程，使得程序能够并发运行。 共享共享是指系统中的">
<meta property="og:locale" content="zh-Hans">
<meta property="og:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img1.jpg">
<meta property="og:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img2.jpg">
<meta property="og:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img3.jpg">
<meta property="og:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img4.jpg">
<meta property="og:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img5.jpg">
<meta property="og:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img6.jpg">
<meta property="og:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img7.jpg">
<meta property="og:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img8.jpg">
<meta property="og:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img9.jpg">
<meta property="og:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img10.jpg">
<meta property="og:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img11.jpg">
<meta property="og:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img12.jpg">
<meta property="og:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img13.jpg">
<meta property="og:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img14.jpg">
<meta property="og:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img15.jpg">
<meta property="og:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img16.jpg">
<meta property="og:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img17.jpg">
<meta property="og:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img18.jpg">
<meta property="og:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img19.jpg">
<meta property="og:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img20.jpg">
<meta property="og:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img21.jpg">
<meta property="og:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img22.jpg">
<meta property="og:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img23.jpg">
<meta property="og:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img24.jpg">
<meta property="og:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img25.jpg">
<meta property="og:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img26.jpg">
<meta property="og:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img27.jpg">
<meta property="og:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img28.jpg">
<meta property="og:updated_time" content="2019-07-25T13:34:36.415Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="操作系统知识点">
<meta name="twitter:description" content="原文地址：搞定操作系统面试，看这篇就够了（一） - Android 2012的文章 - 知乎https://zhuanlan.zhihu.com/p/62219376 概述基本特征并发并发是指宏观上在一段时间内能同时运行多个程序，而并行则指同一时刻能运行多个指令。 并行需要硬件支持，如多流水线、多核处理器或者分布式计算系统。 操作系统通过引入进程和线程，使得程序能够并发运行。 共享共享是指系统中的">
<meta name="twitter:image" content="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/img1.jpg">



  <link rel="alternate" href="/xieyuanhui/atom.xml" title="xieyuanhui的笔记" type="application/atom+xml">



  
  
  <link rel="canonical" href="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/">



<script id="page.configurations">
  CONFIG.page = {
    sidebar: "",
  };
</script>

  <title>操作系统知识点 | xieyuanhui的笔记</title>
  












  <noscript>
  <style>
  .use-motion .motion-element,
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-title { opacity: initial; }

  .use-motion .logo,
  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript><!-- hexo-inject:begin --><!-- hexo-inject:end -->

</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <!-- hexo-inject:begin --><!-- hexo-inject:end --><div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta">
    

    <div class="custom-logo-site-title">
      <a href="/xieyuanhui/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">xieyuanhui的笔记</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
    
    
  </div>

  <div class="site-nav-toggle">
    <button aria-label="切换导航栏">
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>



<nav class="site-nav">
  
    <ul id="menu" class="menu">
      
        
        
        
          
          <li class="menu-item menu-item-home">

    
    
    
      
    

    

    <a href="/xieyuanhui/" rel="section"><i class="menu-item-icon fa fa-fw fa-home"></i> <br>首页</a>

  </li>
        
        
        
          
          <li class="menu-item menu-item-about">

    
    
    
      
    

    

    <a href="/xieyuanhui/about/" rel="section"><i class="menu-item-icon fa fa-fw fa-user"></i> <br>关于</a>

  </li>
        
        
        
          
          <li class="menu-item menu-item-tags">

    
    
    
      
    

    

    <a href="/xieyuanhui/tags/" rel="section"><i class="menu-item-icon fa fa-fw fa-tags"></i> <br>标签</a>

  </li>
        
        
        
          
          <li class="menu-item menu-item-categories">

    
    
    
      
    

    

    <a href="/xieyuanhui/categories/" rel="section"><i class="menu-item-icon fa fa-fw fa-th"></i> <br>分类</a>

  </li>
        
        
        
          
          <li class="menu-item menu-item-archives">

    
    
    
      
    

    

    <a href="/xieyuanhui/archives/" rel="section"><i class="menu-item-icon fa fa-fw fa-archive"></i> <br>归档</a>

  </li>

      
      
        <li class="menu-item menu-item-search">
          
            <a href="javascript:;" class="popup-trigger">
          
            
              <i class="menu-item-icon fa fa-search fa-fw"></i> <br>搜索</a>
        </li>
      
    </ul>
  

  

  
    <div class="site-search">
      
  <div class="popup search-popup local-search-popup">
  <div class="local-search-header clearfix">
    <span class="search-icon">
      <i class="fa fa-search"></i>
    </span>
    <span class="popup-btn-close">
      <i class="fa fa-times-circle"></i>
    </span>
    <div class="local-search-input-wrapper">
      <input autocomplete="off" placeholder="搜索..." spellcheck="false" type="text" id="local-search-input">
    </div>
  </div>
  <div id="local-search-result"></div>
</div>



    </div>
  
</nav>



  



</div>
    </header>

    


    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          
            

          
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://xyh5513.gitee.io/xieyuanhui/xieyuanhui/2019/07/25/操作系统知识点/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="xieyuanhui">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/xieyuanhui/images/deer.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="xieyuanhui的笔记">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">操作系统知识点

              
            
          </h1>
        

        <div class="post-meta">
          <span class="post-time">

            
            
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              

              
                
              

              <time title="创建时间：2019-07-25 16:37:10 / 修改时间：21:34:36" itemprop="dateCreated datePublished" datetime="2019-07-25T16:37:10+08:00">2019-07-25</time>
            

            
              

              
            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing"><a href="/xieyuanhui/categories/操作系统/" itemprop="url" rel="index"><span itemprop="name">操作系统</span></a></span>

                
                
              
            </span>
          

          
            
            
          

          
          
            <span id="/xieyuanhui/2019/07/25/操作系统知识点/" class="leancloud_visitors" data-flag-title="操作系统知识点">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-eye"></i>
              </span>
              
                <span class="post-meta-item-text">阅读次数：</span>
              
                <span class="leancloud-visitors-count"></span>
            </span>
          

          

          
            <div class="post-symbolscount">
              

              
                <span class="post-meta-item-icon">
                  <i class="fa fa-file-word-o"></i>
                </span>
                
                  <span class="post-meta-item-text">本文字数：</span>
                
                <span title="本文字数">20k</span>
              

              
                <span class="post-meta-divider">|</span>
              

              
                <span class="post-meta-item-icon">
                  <i class="fa fa-clock-o"></i>
                </span>
                
                  <span class="post-meta-item-text">阅读时长 &asymp;</span>
                
                <span title="阅读时长">18 分钟</span>
              
            </div>
          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <p>原文地址：搞定操作系统面试，看这篇就够了（一） - Android 2012的文章 - 知乎<br><a href="https://zhuanlan.zhihu.com/p/62219376" target="_blank" rel="noopener">https://zhuanlan.zhihu.com/p/62219376</a></p>
<h2 id="概述"><a href="#概述" class="headerlink" title="概述"></a>概述</h2><h3 id="基本特征"><a href="#基本特征" class="headerlink" title="基本特征"></a>基本特征</h3><h4 id="并发"><a href="#并发" class="headerlink" title="并发"></a>并发</h4><p>并发是指宏观上在一段时间内能同时运行多个程序，而并行则指同一时刻能运行多个指令。</p>
<p>并行需要硬件支持，如多流水线、多核处理器或者分布式计算系统。</p>
<p>操作系统通过引入进程和线程，使得程序能够并发运行。</p>
<h4 id="共享"><a href="#共享" class="headerlink" title="共享"></a>共享</h4><p>共享是指系统中的资源可以被多个并发进程共同使用。</p>
<p>有两种共享方式：互斥共享和同时共享。</p>
<p>互斥共享的资源称为临界资源，例如打印机等，在同一时间只允许一个进程访问，需要用同步机制来实现对临界资源的访问。</p>
<h4 id="虚拟"><a href="#虚拟" class="headerlink" title="虚拟"></a>虚拟</h4><p>虚拟技术把一个物理实体转换为多个逻辑实体。</p>
<p>主要有两种虚拟技术：时分复用技术和空分复用技术。</p>
<p>多个进程能在同一个处理器上并发执行使用了时分复用技术，让每个进程轮流占有处理器，每次只执行一小个时间片并快速切换。</p>
<p>虚拟内存使用了空分复用技术，它将物理内存抽象为地址空间，每个进程都有各自的地址空间。地址空间的页被映射到物理内存，地址空间的页并不需要全部在物理内存中，当使用到一个没有在物理内存的页时，执行页面置换算法，将该页置换到内存中。</p>
<h4 id="异步"><a href="#异步" class="headerlink" title="异步"></a>异步</h4><p>异步指进程不是一次性执行完毕，而是走走停停，以不可知的速度向前推进。</p>
<h3 id="基本功能"><a href="#基本功能" class="headerlink" title="基本功能"></a>基本功能</h3><h4 id="进程管理"><a href="#进程管理" class="headerlink" title="进程管理"></a>进程管理</h4><p>进程控制、进程同步、进程通信、死锁处理、处理机调度等。</p>
<h4 id="内存管理"><a href="#内存管理" class="headerlink" title="内存管理"></a>内存管理</h4><p>内存分配、地址映射、内存保护与共享、虚拟内存等。</p>
<h4 id="文件管理"><a href="#文件管理" class="headerlink" title="文件管理"></a>文件管理</h4><p>文件存储空间的管理、目录管理、文件读写管理和保护等。</p>
<h4 id="设备管理"><a href="#设备管理" class="headerlink" title="设备管理"></a>设备管理</h4><p>完成用户的 I/O 请求，方便用户使用各种设备，并提高设备的利用率。</p>
<p>主要包括缓冲管理、设备分配、设备处理、虛拟设备等。</p>
<h3 id="系统调用"><a href="#系统调用" class="headerlink" title="系统调用"></a>系统调用</h3><p>如果一个进程在用户态需要使用内核态的功能，就进行系统调用从而陷入内核，由操作系统代为完成。</p>
<p><img src="/xieyuanhui/2019/07/25/操作系统知识点/img1.jpg" alt></p>
<p>Linux 的系统调用主要有以下这些：</p>
<p>TaskCommands进程控制fork(); exit(); wait();进程通信pipe(); shmget(); mmap();文件操作open(); read(); write();设备操作ioctl(); read(); write();信息维护getpid(); alarm(); sleep();安全chmod(); umask(); chown();</p>
<h3 id="大内核和微内核"><a href="#大内核和微内核" class="headerlink" title="大内核和微内核"></a>大内核和微内核</h3><h4 id="大内核"><a href="#大内核" class="headerlink" title="大内核"></a>大内核</h4><p>大内核是将操作系统功能作为一个紧密结合的整体放到内核。</p>
<p>由于各模块共享信息，因此有很高的性能。</p>
<h4 id="微内核"><a href="#微内核" class="headerlink" title="微内核"></a>微内核</h4><p>由于操作系统不断复杂，因此将一部分操作系统功能移出内核，从而降低内核的复杂性。移出的部分根据分层的原则划分成若干服务，相互独立。</p>
<p>在微内核结构下，操作系统被划分成小的、定义良好的模块，只有微内核这一个模块运行在内核态，其余模块运行在用户态。</p>
<p>因为需要频繁地在用户态和核心态之间进行切换，所以会有一定的性能损失。</p>
<p><img src="/xieyuanhui/2019/07/25/操作系统知识点/img2.jpg" alt></p>
<h3 id="中断分类"><a href="#中断分类" class="headerlink" title="中断分类"></a>中断分类</h3><h4 id="外中断"><a href="#外中断" class="headerlink" title="外中断"></a>外中断</h4><p>由 CPU 执行指令以外的事件引起，如 I/O 完成中断，表示设备输入/输出处理已经完成，处理器能够发送下一个输入/输出请求。此外还有时钟中断、控制台中断等。</p>
<h4 id="异常"><a href="#异常" class="headerlink" title="异常"></a>异常</h4><p>由 CPU 执行指令的内部事件引起，如非法操作码、地址越界、算术溢出等。</p>
<h4 id="陷入"><a href="#陷入" class="headerlink" title="陷入"></a>陷入</h4><p>在用户程序中使用系统调用。</p>
<h2 id="进程管理-1"><a href="#进程管理-1" class="headerlink" title="进程管理"></a>进程管理</h2><h3 id="进程与线程"><a href="#进程与线程" class="headerlink" title="进程与线程"></a>进程与线程</h3><h4 id="进程"><a href="#进程" class="headerlink" title="进程"></a>进程</h4><p>进程是资源分配的基本单位。</p>
<p>进程控制块 (Process Control Block, PCB) 描述进程的基本信息和运行状态，所谓的创建进程和撤销进程，都是指对 PCB 的操作。</p>
<p>下图显示了 4 个程序创建了 4 个进程，这 4 个进程可以并发地执行。</p>
<p><img src="/xieyuanhui/2019/07/25/操作系统知识点/img3.jpg" alt></p>
<h4 id="线程"><a href="#线程" class="headerlink" title="线程"></a>线程</h4><p>线程是独立调度的基本单位。</p>
<p>一个进程中可以有多个线程，它们共享进程资源。</p>
<p>QQ 和浏览器是两个进程，浏览器进程里面有很多线程，例如 HTTP 请求线程、事件响应线程、渲染线程等等，线程的并发执行使得在浏览器中点击一个新链接从而发起 HTTP 请求时，浏览器还可以响应用户的其它事件。</p>
<p><img src="/xieyuanhui/2019/07/25/操作系统知识点/img4.jpg" alt></p>
<h4 id="区别"><a href="#区别" class="headerlink" title="区别"></a>区别</h4><p>Ⅰ 拥有资源</p>
<p>进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源。</p>
<p>Ⅱ 调度</p>
<p>线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。</p>
<p>Ⅲ 系统开销</p>
<p>由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。</p>
<p>Ⅳ 通信方面</p>
<p>线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助 IPC。</p>
<h3 id="进程状态切换"><a href="#进程状态切换" class="headerlink" title="进程状态切换"></a>进程状态切换</h3><p><img src="/xieyuanhui/2019/07/25/操作系统知识点/img5.jpg" alt></p>
<ul>
<li>就绪状态（ready）：等待被调度</li>
<li>运行状态（running）</li>
<li>阻塞状态（waiting）：等待资源</li>
</ul>
<p>应该注意以下内容：</p>
<ul>
<li>只有就绪态和运行态可以相互转换，其它的都是单向转换。就绪状态的进程通过调度算法从而获得 CPU 时间，转为运行状态；而运行状态的进程，在分配给它的 CPU 时间片用完之后就会转为就绪状态，等待下一次调度。</li>
<li>阻塞状态是缺少需要的资源从而由运行状态转换而来，但是该资源不包括 CPU 时间，缺少 CPU 时间会从运行态转换为就绪态。</li>
</ul>
<h3 id="进程调度算法"><a href="#进程调度算法" class="headerlink" title="进程调度算法"></a>进程调度算法</h3><p>不同环境的调度算法目标不同，因此需要针对不同环境来讨论调度算法。</p>
<h4 id="批处理系统"><a href="#批处理系统" class="headerlink" title="批处理系统"></a>批处理系统</h4><p>批处理系统没有太多的用户操作，在该系统中，调度算法目标是保证吞吐量和周转时间（从提交到终止的时间）。</p>
<h5 id="先来先服务-first-come-first-serverd（FCFS）"><a href="#先来先服务-first-come-first-serverd（FCFS）" class="headerlink" title="先来先服务 first-come first-serverd（FCFS）"></a>先来先服务 first-come first-serverd（FCFS）</h5><p>按照请求的顺序进行调度。</p>
<p>有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。</p>
<h5 id="短作业优先-shortest-job-first（SJF）"><a href="#短作业优先-shortest-job-first（SJF）" class="headerlink" title="短作业优先 shortest job first（SJF）"></a>短作业优先 shortest job first（SJF）</h5><p>按估计运行时间最短的顺序进行调度。</p>
<p>长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。</p>
<h5 id="最短剩余时间优先-shortest-remaining-time-next（SRTN）"><a href="#最短剩余时间优先-shortest-remaining-time-next（SRTN）" class="headerlink" title="最短剩余时间优先 shortest remaining time next（SRTN）"></a>最短剩余时间优先 shortest remaining time next（SRTN）</h5><p>按估计剩余时间最短的顺序进行调度。</p>
<h4 id="交互式系统"><a href="#交互式系统" class="headerlink" title="交互式系统"></a>交互式系统</h4><p>交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速地进行响应。</p>
<h5 id="时间片轮转"><a href="#时间片轮转" class="headerlink" title="时间片轮转"></a>时间片轮转</h5><p>将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。</p>
<p>时间片轮转算法的效率和时间片的大小有很大关系：</p>
<ul>
<li>因为进程切换都要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。</li>
<li>而如果时间片过长，那么实时性就不能得到保证。</li>
</ul>
<p><img src="/xieyuanhui/2019/07/25/操作系统知识点/img6.jpg" alt></p>
<h5 id="优先级调度"><a href="#优先级调度" class="headerlink" title="优先级调度"></a>优先级调度</h5><p>为每个进程分配一个优先级，按优先级进行调度。</p>
<p>为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。</p>
<h5 id="多级反馈队列"><a href="#多级反馈队列" class="headerlink" title="多级反馈队列"></a>多级反馈队列</h5><p>一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。</p>
<p>多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,..。进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，之前的进程只需要交换 7 次。</p>
<p>每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。</p>
<p>可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。</p>
<p><img src="/xieyuanhui/2019/07/25/操作系统知识点/img7.jpg" alt></p>
<h4 id="实时系统"><a href="#实时系统" class="headerlink" title="实时系统"></a>实时系统</h4><p>实时系统要求一个请求在一个确定时间内得到响应。</p>
<p>分为硬实时和软实时，前者必须满足绝对的截止时间，后者可以容忍一定的超时。</p>
<h3 id="进程同步"><a href="#进程同步" class="headerlink" title="进程同步"></a>进程同步</h3><h4 id="临界区"><a href="#临界区" class="headerlink" title="临界区"></a>临界区</h4><p>对临界资源进行访问的那段代码称为临界区。</p>
<p>为了互斥访问临界资源，每个进程在进入临界区之前，需要先进行检查。</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// entry section</span></span><br><span class="line"><span class="comment">// critical section;</span></span><br><span class="line"><span class="comment">// exit section</span></span><br></pre></td></tr></table></figure>
<h4 id="同步与互斥"><a href="#同步与互斥" class="headerlink" title="同步与互斥"></a>同步与互斥</h4><ul>
<li>同步：多个进程按一定顺序执行；</li>
<li>互斥：多个进程在同一时刻只有一个进程能进入临界区。</li>
</ul>
<h4 id="信号量"><a href="#信号量" class="headerlink" title="信号量"></a>信号量</h4><p>信号量（Semaphore）是一个整型变量，可以对其执行 down 和 up 操作，也就是常见的 P 和 V 操作。</p>
<ul>
<li><strong>down</strong> : 如果信号量大于 0 ，执行 -1 操作；如果信号量等于 0，进程睡眠，等待信号量大于 0；</li>
<li><strong>up</strong> ：对信号量执行 +1 操作，唤醒睡眠的进程让其完成 down 操作。</li>
</ul>
<p>down 和 up 操作需要被设计成原语，不可分割，通常的做法是在执行这些操作的时候屏蔽中断。</p>
<p>如果信号量的取值只能为 0 或者 1，那么就成为了 <strong>互斥量（Mutex）</strong> ，0 表示临界区已经加锁，1 表示临界区解锁。</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">typedef</span> <span class="keyword">int</span> semaphore;</span><br><span class="line">semaphore mutex = <span class="number">1</span>;</span><br><span class="line">   <span class="function"><span class="keyword">void</span> <span class="title">P1</span><span class="params">()</span> </span>&#123;</span><br><span class="line">   down(&amp;mutex);</span><br><span class="line">   <span class="comment">// 临界区</span></span><br><span class="line">   up(&amp;mutex);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">P2</span><span class="params">()</span> </span>&#123;</span><br><span class="line">   down(&amp;mutex);</span><br><span class="line">   <span class="comment">// 临界区</span></span><br><span class="line">   up(&amp;mutex);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>使用信号量实现生产者-消费者问题</p>
<p>问题描述：使用一个缓冲区来保存物品，只有缓冲区没有满，生产者才可以放入物品；只有缓冲区不为空，消费者才可以拿走物品。</p>
<p>因为缓冲区属于临界资源，因此需要使用一个互斥量 mutex 来控制对缓冲区的互斥访问。</p>
<p>为了同步生产者和消费者的行为，需要记录缓冲区中物品的数量。数量可以使用信号量来进行统计，这里需要使用两个信号量：empty 记录空缓冲区的数量，full 记录满缓冲区的数量。其中，empty 信号量是在生产者进程中使用，当 empty 不为 0 时，生产者才可以放入物品；full 信号量是在消费者进程中使用，当 full 信号量不为 0 时，消费者才可以取走物品。</p>
<p>注意，不能先对缓冲区进行加锁，再测试信号量。也就是说，不能先执行 down(mutex) 再执行 down(empty)。如果这么做了，那么可能会出现这种情况：生产者对缓冲区加锁后，执行 down(empty) 操作，发现 empty = 0，此时生产者睡眠。消费者不能进入临界区，因为生产者对缓冲区加锁了，消费者就无法执行 up(empty) 操作，empty 永远都为 0，导致生产者永远等待下，不会释放锁，消费者因此也会永远等待下去。</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">define</span> N 100</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">int</span> semaphore;</span><br><span class="line">semaphore mutex = <span class="number">1</span>;</span><br><span class="line">semaphore empty = N;</span><br><span class="line">semaphore full = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">producer</span><span class="params">()</span> </span>&#123;</span><br><span class="line">   <span class="keyword">while</span>(TRUE) &#123;</span><br><span class="line">      <span class="keyword">int</span> item = produce_item();</span><br><span class="line">      down(&amp;empty);</span><br><span class="line">      down(&amp;mutex);</span><br><span class="line">      insert_item(item);</span><br><span class="line">      up(&amp;mutex);</span><br><span class="line">      up(&amp;full);</span><br><span class="line">   &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">consumer</span><span class="params">()</span> </span>&#123;</span><br><span class="line">   <span class="keyword">while</span>(TRUE) &#123;</span><br><span class="line">      down(&amp;full);</span><br><span class="line">      down(&amp;mutex);</span><br><span class="line">      <span class="keyword">int</span> item = remove_item();</span><br><span class="line">      consume_item(item);</span><br><span class="line">      up(&amp;mutex);</span><br><span class="line">      up(&amp;empty);</span><br><span class="line">   &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="管程"><a href="#管程" class="headerlink" title="管程"></a>管程</h4><p>使用信号量机制实现的生产者消费者问题需要客户端代码做很多控制，而管程把控制的代码独立出来，不仅不容易出错，也使得客户端代码调用更容易。</p>
<p>c 语言不支持管程，下面的示例代码使用了类 Pascal 语言来描述管程。示例代码的管程提供了 insert() 和 remove() 方法，客户端代码通过调用这两个方法来解决生产者-消费者问题。</p>
<figure class="highlight pascal"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line">monitor ProducerConsumer</span><br><span class="line">   integer i;</span><br><span class="line">   condition c;</span><br><span class="line">   </span><br><span class="line">   <span class="function"><span class="keyword">procedure</span> <span class="title">insert</span><span class="params">()</span>;</span></span><br><span class="line">   <span class="keyword">begin</span></span><br><span class="line">      <span class="comment">// ...</span></span><br><span class="line">   <span class="keyword">end</span>;</span><br><span class="line">   </span><br><span class="line">   <span class="function"><span class="keyword">procedure</span> <span class="title">remove</span><span class="params">()</span>;</span></span><br><span class="line">   <span class="keyword">begin</span></span><br><span class="line">      <span class="comment">// ...</span></span><br><span class="line">   <span class="keyword">end</span>;</span><br><span class="line"><span class="keyword">end</span> monitor;</span><br></pre></td></tr></table></figure>
<p>管程有一个重要特性：在一个时刻只能有一个进程使用管程。进程在无法继续执行的时候不能一直占用管程，否者其它进程永远不能使用管程。</p>
<p>管程引入了 <strong>条件变量</strong> 以及相关的操作：<strong>wait()</strong> 和 <strong>signal()</strong> 来实现同步操作。对条件变量执行 wait() 操作会导致调用进程阻塞，把管程让出来给另一个进程持有。signal() 操作用于唤醒被阻塞的进程。</p>
<p>使用管程实现生产者-消费者问题</p>
<figure class="highlight pascal"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 管程// 管程</span></span><br><span class="line">monitor ProducerConsumer</span><br><span class="line">   condition full, empty;</span><br><span class="line">   integer count := <span class="number">0</span>;</span><br><span class="line">      condition c;</span><br><span class="line"></span><br><span class="line">   <span class="function"><span class="keyword">procedure</span> <span class="title">insert</span><span class="params">(item: integer)</span>;</span></span><br><span class="line">   <span class="keyword">begin</span></span><br><span class="line">      <span class="keyword">if</span> count = N <span class="keyword">then</span> wait(full);</span><br><span class="line">      insert_item(item);</span><br><span class="line">      count := count + <span class="number">1</span>;</span><br><span class="line">      <span class="keyword">if</span> count = <span class="number">1</span> <span class="keyword">then</span> signal(empty);</span><br><span class="line">   <span class="keyword">end</span>;</span><br><span class="line"></span><br><span class="line">   <span class="function"><span class="keyword">function</span> <span class="title">remove</span>:</span> integer;</span><br><span class="line">   <span class="keyword">begin</span></span><br><span class="line">      <span class="keyword">if</span> count = <span class="number">0</span> <span class="keyword">then</span> wait(empty);</span><br><span class="line">      remove = remove_item;</span><br><span class="line">      count := count - <span class="number">1</span>;</span><br><span class="line">      <span class="keyword">if</span> count = N -<span class="number">1</span> <span class="keyword">then</span> signal(full);</span><br><span class="line">   <span class="keyword">end</span>;</span><br><span class="line"><span class="keyword">end</span> monitor;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 生产者客户端</span></span><br><span class="line"><span class="function"><span class="keyword">procedure</span> <span class="title">producer</span></span></span><br><span class="line"><span class="function"><span class="title">begin</span></span></span><br><span class="line"><span class="function">   <span class="title">while</span> <span class="title">true</span> <span class="title">do</span></span></span><br><span class="line"><span class="function">   <span class="title">begin</span></span></span><br><span class="line"><span class="function">      <span class="title">item</span> = <span class="title">produce_item</span>;</span></span><br><span class="line">      ProducerConsumer.insert(item);</span><br><span class="line">   <span class="keyword">end</span></span><br><span class="line"><span class="keyword">end</span>;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 消费者客户端</span></span><br><span class="line"><span class="function"><span class="keyword">procedure</span> <span class="title">consumer</span></span></span><br><span class="line"><span class="function"><span class="title">begin</span></span></span><br><span class="line"><span class="function">   <span class="title">while</span> <span class="title">true</span> <span class="title">do</span></span></span><br><span class="line"><span class="function">   <span class="title">begin</span></span></span><br><span class="line"><span class="function">      <span class="title">item</span> = <span class="title">ProducerConsumer</span>.<span class="title">remove</span>;</span></span><br><span class="line">      consume_item(item);</span><br><span class="line">   <span class="keyword">end</span></span><br><span class="line"><span class="keyword">end</span>;</span><br></pre></td></tr></table></figure>
<h4 id="经典同步问题"><a href="#经典同步问题" class="headerlink" title="经典同步问题"></a>经典同步问题</h4><h5 id="读者-写者问题"><a href="#读者-写者问题" class="headerlink" title="读者-写者问题"></a>读者-写者问题</h5><p>允许多个进程同时对数据进行读操作，但是不允许读和写以及写和写操作同时发生。</p>
<p>一个整型变量 count 记录在对数据进行读操作的进程数量，一个互斥量 count_mutex 用于对 count 加锁，一个互斥量 data_mutex 用于对读写的数据加锁。</p>
<figure class="highlight pascal"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line">typedef int semaphore;</span><br><span class="line">semaphore count_mutex = <span class="number">1</span>;</span><br><span class="line">semaphore data_mutex = <span class="number">1</span>;</span><br><span class="line">int count = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">void reader() <span class="comment">&#123;</span></span><br><span class="line"><span class="comment">   while(TRUE) &#123;</span></span><br><span class="line"><span class="comment">      down(&amp;count_mutex);</span></span><br><span class="line"><span class="comment">      count++;</span></span><br><span class="line"><span class="comment">      if(count == 1) down(&amp;data_mutex); // 第一个读者需要对数据进行加锁，防止写进程访问</span></span><br><span class="line"><span class="comment">      up(&amp;count_mutex);</span></span><br><span class="line"><span class="comment">      read();</span></span><br><span class="line"><span class="comment">      down(&amp;count_mutex);</span></span><br><span class="line"><span class="comment">      count--;</span></span><br><span class="line"><span class="comment">      if(count == 0) up(&amp;data_mutex);</span></span><br><span class="line"><span class="comment">      up(&amp;count_mutex);</span></span><br><span class="line"><span class="comment">   &#125;</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">void writer() <span class="comment">&#123;</span></span><br><span class="line"><span class="comment">   while(TRUE) &#123;</span></span><br><span class="line"><span class="comment">      down(&amp;data_mutex);</span></span><br><span class="line"><span class="comment">      write();</span></span><br><span class="line"><span class="comment">      up(&amp;data_mutex);</span></span><br><span class="line"><span class="comment">   &#125;</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>以下内容由 @Bandi Yugandhar 提供。</p>
<p>The first case may result Writer to starve. This case favous Writers i.e no writer, once added to the queue, shall be kept waiting longer than absolutely necessary(only when there are readers that entered the queue before the writer).</p>
<figure class="highlight pascal"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//READER</span></span><br><span class="line">void reader() <span class="comment">&#123;</span></span><br><span class="line"><span class="comment">&lt;ENTRY Section&gt;</span></span><br><span class="line"><span class="comment">   down(&amp;readLock);                 //  reader is trying to enter</span></span><br><span class="line"><span class="comment">   down(&amp;rmutex);                  //   lock to increase readcount</span></span><br><span class="line"><span class="comment">   readcount++;</span></span><br><span class="line"><span class="comment">   if (readcount == 1)</span></span><br><span class="line"><span class="comment">      down(&amp;resource);              //if you are the first reader then lock  the resource</span></span><br><span class="line"><span class="comment">   up(&amp;rmutex);                  //release  for other readers</span></span><br><span class="line"><span class="comment">   up(&amp;readLock);                 //Done with trying to access the resource</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">&lt;CRITICAL Section&gt;</span></span><br><span class="line"><span class="comment">//reading is performed</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">&lt;EXIT Section&gt;</span></span><br><span class="line"><span class="comment">   down(&amp;rmutex);                  //reserve exit section - avoids race condition with readers</span></span><br><span class="line"><span class="comment">   readcount--;                       //indicate you're leaving</span></span><br><span class="line"><span class="comment">   if (readcount == 0)          //checks if you are last reader leaving</span></span><br><span class="line"><span class="comment">      up(&amp;resource);              //if last, you must release the locked resource</span></span><br><span class="line"><span class="comment">   up(&amp;rmutex);                  //release exit section for other readers</span></span><br><span class="line"><span class="comment">&#125;</span></span><br><span class="line"></span><br><span class="line"><span class="comment">//WRITER</span></span><br><span class="line">void writer() <span class="comment">&#123;</span></span><br><span class="line"><span class="comment">&lt;ENTRY Section&gt;</span></span><br><span class="line"><span class="comment">   down(&amp;wmutex);                  //reserve entry section for writers - avoids race conditions</span></span><br><span class="line"><span class="comment">   writecount++;                //report yourself as a writer entering</span></span><br><span class="line"><span class="comment">   if (writecount == 1)         //checks if you're first writer</span></span><br><span class="line"><span class="comment">      down(&amp;readLock);               //if you're first, then you must lock the readers out. Prevent them from trying to enter CS</span></span><br><span class="line"><span class="comment">   up(&amp;wmutex);                  //release entry section</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">&lt;CRITICAL Section&gt;</span></span><br><span class="line"><span class="comment">   down(&amp;resource);                //reserve the resource for yourself - prevents other writers from simultaneously editing the shared resource</span></span><br><span class="line"><span class="comment">   //writing is performed</span></span><br><span class="line"><span class="comment">   up(&amp;resource);                //release file</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">&lt;EXIT Section&gt;</span></span><br><span class="line"><span class="comment">   down(&amp;wmutex);                  //reserve exit section</span></span><br><span class="line"><span class="comment">   writecount--;                //indicate you're leaving</span></span><br><span class="line"><span class="comment">   if (writecount == 0)         //checks if you're the last writer</span></span><br><span class="line"><span class="comment">      up(&amp;readLock);               //if you're last writer, you must unlock the readers. Allows them to try enter CS for reading</span></span><br><span class="line"><span class="comment">   up(&amp;wmutex);                  //release exit section</span></span><br><span class="line"><span class="comment">&#125;</span></span><br></pre></td></tr></table></figure>
<p>We can observe that every reader is forced to acquire ReadLock. On the otherhand, writers doesn’t need to lock individually. Once the first writer locks the ReadLock, it will be released only when there is no writer left in the queue.</p>
<p>From the both cases we observed that either reader or writer has to starve. Below solutionadds the constraint that no thread shall be allowed to starve; that is, the operation of obtaining a lock on the shared data will always terminate in a bounded amount of time.</p>
<figure class="highlight pascal"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br></pre></td><td class="code"><pre><span class="line">int readcount, writecount;                   <span class="comment">//(initial value = 0)</span></span><br><span class="line">semaphore rmutex, wmutex, readLock, resource; <span class="comment">//(initial value = 1)</span></span><br><span class="line"></span><br><span class="line">int readCount;                  <span class="comment">// init to 0; number of readers currently accessing resource</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// all semaphores initialised to 1</span></span><br><span class="line">Semaphore resourceAccess;       <span class="comment">// controls access (read/write) to the resource</span></span><br><span class="line">Semaphore readCountAccess;      <span class="comment">// for syncing changes to shared variable readCount</span></span><br><span class="line">Semaphore serviceQueue;         <span class="comment">// FAIRNESS: preserves ordering of requests (signaling must be FIFO)</span></span><br><span class="line"></span><br><span class="line">void writer()</span><br><span class="line"><span class="comment">&#123;</span></span><br><span class="line"><span class="comment">   down(&amp;serviceQueue);           // wait in line to be servicexs</span></span><br><span class="line"><span class="comment">   // &lt;ENTER&gt;</span></span><br><span class="line"><span class="comment">   down(&amp;resourceAccess);         // request exclusive access to resource</span></span><br><span class="line"><span class="comment">   // &lt;/ENTER&gt;</span></span><br><span class="line"><span class="comment">   up(&amp;serviceQueue);           // let next in line be serviced</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">   // &lt;WRITE&gt;</span></span><br><span class="line"><span class="comment">   writeResource();            // writing is performed</span></span><br><span class="line"><span class="comment">   // &lt;/WRITE&gt;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">   // &lt;EXIT&gt;</span></span><br><span class="line"><span class="comment">   up(&amp;resourceAccess);         // release resource access for next reader/writer</span></span><br><span class="line"><span class="comment">   // &lt;/EXIT&gt;</span></span><br><span class="line"><span class="comment">&#125;</span></span><br><span class="line"></span><br><span class="line">void reader()</span><br><span class="line"><span class="comment">&#123;</span></span><br><span class="line"><span class="comment">   down(&amp;serviceQueue);           // wait in line to be serviced</span></span><br><span class="line"><span class="comment">   down(&amp;readCountAccess);        // request exclusive access to readCount</span></span><br><span class="line"><span class="comment">   // &lt;ENTER&gt;</span></span><br><span class="line"><span class="comment">   if (readCount == 0)         // if there are no readers already reading:</span></span><br><span class="line"><span class="comment">      down(&amp;resourceAccess);     // request resource access for readers (writers blocked)</span></span><br><span class="line"><span class="comment">   readCount++;                // update count of active readers</span></span><br><span class="line"><span class="comment">   // &lt;/ENTER&gt;</span></span><br><span class="line"><span class="comment">   up(&amp;serviceQueue);           // let next in line be serviced</span></span><br><span class="line"><span class="comment">   up(&amp;readCountAccess);        // release access to readCount</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">   // &lt;READ&gt;</span></span><br><span class="line"><span class="comment">   readResource();             // reading is performed</span></span><br><span class="line"><span class="comment">   // &lt;/READ&gt;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">   down(&amp;readCountAccess);        // request exclusive access to readCount</span></span><br><span class="line"><span class="comment">   // &lt;EXIT&gt;</span></span><br><span class="line"><span class="comment">   readCount--;                // update count of active readers</span></span><br><span class="line"><span class="comment">   if (readCount == 0)         // if there are no readers left:</span></span><br><span class="line"><span class="comment">      up(&amp;resourceAccess);     // release resource access for all</span></span><br><span class="line"><span class="comment">   // &lt;/EXIT&gt;</span></span><br><span class="line"><span class="comment">   up(&amp;readCountAccess);        // release access to readCount</span></span><br><span class="line"><span class="comment">&#125;</span></span><br></pre></td></tr></table></figure>
<h5 id="哲学家进餐问题"><a href="#哲学家进餐问题" class="headerlink" title="哲学家进餐问题"></a>哲学家进餐问题</h5><p><img src="/xieyuanhui/2019/07/25/操作系统知识点/img8.jpg" alt></p>
<p>五个哲学家围着一张圆桌，每个哲学家面前放着食物。哲学家的生活有两种交替活动：吃饭以及思考。当一个哲学家吃饭时，需要先拿起自己左右两边的两根筷子，并且一次只能拿起一根筷子。</p>
<p>下面是一种错误的解法，考虑到如果所有哲学家同时拿起左手边的筷子，那么就无法拿起右手边的筷子，造成死锁。</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">define</span> N 5</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">philosopher</span><span class="params">(<span class="keyword">int</span> i)</span> </span>&#123;</span><br><span class="line">   <span class="keyword">while</span>(TRUE) &#123;</span><br><span class="line">      think();</span><br><span class="line">      take(i);       <span class="comment">// 拿起左边的筷子</span></span><br><span class="line">      take((i+<span class="number">1</span>)%N); <span class="comment">// 拿起右边的筷子</span></span><br><span class="line">      eat();</span><br><span class="line">      put(i);</span><br><span class="line">      put((i+<span class="number">1</span>)%N);</span><br><span class="line">   &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>为了防止死锁的发生，可以设置两个条件：</p>
<ul>
<li>必须同时拿起左右两根筷子；</li>
<li>只有在两个邻居都没有进餐的情况下才允许进餐。</li>
</ul>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">define</span> N 5</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> LEFT (i + N - 1) % N <span class="comment">// 左邻居</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> RIGHT (i + 1) % N    <span class="comment">// 右邻居</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> THINKING 0</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> HUNGRY   1</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> EATING   2</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">int</span> semaphore;</span><br><span class="line"><span class="keyword">int</span> state[N];                <span class="comment">// 跟踪每个哲学家的状态</span></span><br><span class="line">semaphore mutex = <span class="number">1</span>;         <span class="comment">// 临界区的互斥</span></span><br><span class="line">semaphore s[N];              <span class="comment">// 每个哲学家一个信号量</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">philosopher</span><span class="params">(<span class="keyword">int</span> i)</span> </span>&#123;</span><br><span class="line">   <span class="keyword">while</span>(TRUE) &#123;</span><br><span class="line">      think();</span><br><span class="line">      take_two(i);</span><br><span class="line">      eat();</span><br><span class="line">      put_two(i);</span><br><span class="line">   &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">take_two</span><span class="params">(<span class="keyword">int</span> i)</span> </span>&#123;</span><br><span class="line">   down(&amp;mutex);</span><br><span class="line">   state[i] = HUNGRY;</span><br><span class="line">   test(i);</span><br><span class="line">   up(&amp;mutex);</span><br><span class="line">   down(&amp;s[i]);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">put_two</span><span class="params">(i)</span> </span>&#123;</span><br><span class="line">   down(&amp;mutex);</span><br><span class="line">   state[i] = THINKING;</span><br><span class="line">   test(LEFT);</span><br><span class="line">   test(RIGHT);</span><br><span class="line">   up(&amp;mutex);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">test</span><span class="params">(i)</span> </span>&#123;         <span class="comment">// 尝试拿起两把筷子</span></span><br><span class="line">   <span class="keyword">if</span>(state[i] == HUNGRY &amp;&amp; state[LEFT] != EATING &amp;&amp; state[RIGHT] !=EATING) &#123;</span><br><span class="line">   state[i] = EATING;</span><br><span class="line">   up(&amp;s[i]);</span><br><span class="line">   &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="进程通信"><a href="#进程通信" class="headerlink" title="进程通信"></a>进程通信</h3><p>进程同步与进程通信很容易混淆，它们的区别在于：</p>
<ul>
<li>进程同步：控制多个进程按一定顺序执行；</li>
<li>进程通信：进程间传输信息。</li>
</ul>
<p>进程通信是一种手段，而进程同步是一种目的。也可以说，为了能够达到进程同步的目的，需要让进程进行通信，传输一些进程同步所需要的信息。</p>
<h4 id="管道"><a href="#管道" class="headerlink" title="管道"></a>管道</h4><p>管道是通过调用 pipe 函数创建的，fd[0] 用于读，fd[1] 用于写。</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;unistd.h&gt;</span></span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">pipe</span><span class="params">(<span class="keyword">int</span> fd[<span class="number">2</span>])</span></span>;</span><br></pre></td></tr></table></figure>
<p>它具有以下限制：</p>
<ul>
<li>只支持半双工通信（单向交替传输）；</li>
<li>只能在父子进程中使用。</li>
</ul>
<p><img src="/xieyuanhui/2019/07/25/操作系统知识点/img9.jpg" alt></p>
<h4 id="FIFO"><a href="#FIFO" class="headerlink" title="FIFO"></a>FIFO</h4><p>也称为命名管道，去除了管道只能在父子进程中使用的限制。</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;sys/stat.h&gt;</span></span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">mkfifo</span><span class="params">(<span class="keyword">const</span> <span class="keyword">char</span> *path, <span class="keyword">mode_t</span> mode)</span></span>;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">mkfifoat</span><span class="params">(<span class="keyword">int</span> fd, <span class="keyword">const</span> <span class="keyword">char</span> *path, <span class="keyword">mode_t</span> mode)</span></span>;</span><br></pre></td></tr></table></figure>
<p>FIFO 常用于客户-服务器应用程序中，FIFO 用作汇聚点，在客户进程和服务器进程之间传递数据。</p>
<p><img src="/xieyuanhui/2019/07/25/操作系统知识点/img10.jpg" alt></p>
<h4 id="消息队列"><a href="#消息队列" class="headerlink" title="消息队列"></a>消息队列</h4><p>相比于 FIFO，消息队列具有以下优点：</p>
<ul>
<li>消息队列可以独立于读写进程存在，从而避免了 FIFO 中同步管道的打开和关闭时可能产生的困难；</li>
<li>避免了 FIFO 的同步阻塞问题，不需要进程自己提供同步方法；</li>
<li>读进程可以根据消息类型有选择地接收消息，而不像 FIFO 那样只能默认地接收。</li>
</ul>
<h4 id="信号量-1"><a href="#信号量-1" class="headerlink" title="信号量"></a>信号量</h4><p>它是一个计数器，用于为多个进程提供对共享数据对象的访问。</p>
<h4 id="存储共享"><a href="#存储共享" class="headerlink" title="存储共享"></a>存储共享</h4><p>允许多个进程共享一个给定的存储区。因为数据不需要在进程之间复制，所以这是最快的一种 IPC。</p>
<p>需要使用信号量用来同步对共享存储的访问。</p>
<p>多个进程可以将同一个文件映射到它们的地址空间从而实现共享内存。另外 XSI 共享内存不是使用文件，而是使用使用内存的匿名段。</p>
<h4 id="套接字"><a href="#套接字" class="headerlink" title="套接字"></a>套接字</h4><p>与其它通信机制不同的是，它可用于不同机器间的进程通信。</p>
<h2 id="死锁"><a href="#死锁" class="headerlink" title="死锁"></a>死锁</h2><h3 id="必要条件"><a href="#必要条件" class="headerlink" title="必要条件"></a>必要条件</h3><p><img src="/xieyuanhui/2019/07/25/操作系统知识点/img11.jpg" alt></p>
<ul>
<li>互斥：每个资源要么已经分配给了一个进程，要么就是可用的。</li>
<li>占有和等待：已经得到了某个资源的进程可以再请求新的资源。</li>
<li>不可抢占：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放。</li>
<li>环路等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。</li>
</ul>
<h3 id="处理方法"><a href="#处理方法" class="headerlink" title="处理方法"></a>处理方法</h3><p>主要有以下四种方法：</p>
<ul>
<li>鸵鸟策略</li>
<li>死锁检测与死锁恢复</li>
<li>死锁预防</li>
<li>死锁避免</li>
</ul>
<h4 id="鸵鸟策略"><a href="#鸵鸟策略" class="headerlink" title="鸵鸟策略"></a>鸵鸟策略</h4><p>把头埋在沙子里，假装根本没发生问题。</p>
<p>因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。</p>
<p>当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。</p>
<p>大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。</p>
<h4 id="死锁检测与死锁恢复"><a href="#死锁检测与死锁恢复" class="headerlink" title="死锁检测与死锁恢复"></a>死锁检测与死锁恢复</h4><p>不试图阻止死锁，而是当检测到死锁发生时，采取措施进行恢复。</p>
<h5 id="每种类型一个资源的死锁检测"><a href="#每种类型一个资源的死锁检测" class="headerlink" title="每种类型一个资源的死锁检测"></a>每种类型一个资源的死锁检测</h5><p><img src="/xieyuanhui/2019/07/25/操作系统知识点/img12.jpg" alt></p>
<p>上图为资源分配图，其中方框表示资源，圆圈表示进程。资源指向进程表示该资源已经分配给该进程，进程指向资源表示进程请求获取该资源。</p>
<p>图 a 可以抽取出环，如图 b，它满足了环路等待条件，因此会发生死锁。</p>
<p>每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。</p>
<h5 id="每种类型多个资源的死锁检测"><a href="#每种类型多个资源的死锁检测" class="headerlink" title="每种类型多个资源的死锁检测"></a>每种类型多个资源的死锁检测</h5><p><img src="/xieyuanhui/2019/07/25/操作系统知识点/img13.jpg" alt></p>
<p>上图中，有三个进程四个资源，每个数据代表的含义如下：</p>
<ul>
<li>E 向量：资源总量</li>
<li>A 向量：资源剩余量</li>
<li>C 矩阵：每个进程所拥有的资源数量，每一行都代表一个进程拥有资源的数量</li>
<li>R 矩阵：每个进程请求的资源数量</li>
</ul>
<p>进程 P1 和 P2 所请求的资源都得不到满足，只有进程 P3 可以，让 P3 执行，之后释放 P3 拥有的资源，此时 A = (2 2 2 0)。P2 可以执行，执行后释放 P2 拥有的资源，A = (4 2 2 1) 。P1 也可以执行。所有进程都可以顺利执行，没有死锁。</p>
<p>算法总结如下：</p>
<p>每个进程最开始时都不被标记，执行过程有可能被标记。当算法结束时，任何没有被标记的进程都是死锁进程。</p>
<ol>
<li>寻找一个没有标记的进程 Pi，它所请求的资源小于等于 A。</li>
<li>如果找到了这样一个进程，那么将 C 矩阵的第 i 行向量加到 A 中，标记该进程，并转回 1。</li>
<li>如果没有这样一个进程，算法终止。</li>
</ol>
<h5 id="死锁恢复"><a href="#死锁恢复" class="headerlink" title="死锁恢复"></a>死锁恢复</h5><ul>
<li>利用抢占恢复</li>
<li>利用回滚恢复</li>
<li>通过杀死进程恢复</li>
</ul>
<h4 id="死锁预防"><a href="#死锁预防" class="headerlink" title="死锁预防"></a>死锁预防</h4><p>在程序运行之前预防发生死锁。</p>
<h5 id="破坏互斥条件"><a href="#破坏互斥条件" class="headerlink" title="破坏互斥条件"></a>破坏互斥条件</h5><p>例如假脱机打印机技术允许若干个进程同时输出，唯一真正请求物理打印机的进程是打印机守护进程。</p>
<h5 id="破坏占有和等待条件"><a href="#破坏占有和等待条件" class="headerlink" title="破坏占有和等待条件"></a>破坏占有和等待条件</h5><p>一种实现方式是规定所有进程在开始执行前请求所需要的全部资源。</p>
<h5 id="破坏不可抢占条件"><a href="#破坏不可抢占条件" class="headerlink" title="破坏不可抢占条件"></a>破坏不可抢占条件</h5><h5 id="破坏环路等待"><a href="#破坏环路等待" class="headerlink" title="破坏环路等待"></a>破坏环路等待</h5><p>给资源统一编号，进程只能按编号顺序来请求资源。</p>
<h4 id="死锁避免"><a href="#死锁避免" class="headerlink" title="死锁避免"></a>死锁避免</h4><p>在程序运行时避免发生死锁。</p>
<h5 id="安全状态"><a href="#安全状态" class="headerlink" title="安全状态"></a>安全状态</h5><p><img src="/xieyuanhui/2019/07/25/操作系统知识点/img14.jpg" alt></p>
<p>图 a 的第二列 Has 表示已拥有的资源数，第三列 Max 表示总共需要的资源数，Free 表示还有可以使用的资源数。从图 a 开始出发，先让 B 拥有所需的所有资源（图 b），运行结束后释放 B，此时 Free 变为 5（图 c）；接着以同样的方式运行 C 和 A，使得所有进程都能成功运行，因此可以称图 a 所示的状态时安全的。</p>
<p>定义：如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。</p>
<p>安全状态的检测与死锁的检测类似，因为安全状态必须要求不能发生死锁。下面的银行家算法与死锁检测算法非常类似，可以结合着做参考对比。</p>
<h5 id="单个资源的银行家算法"><a href="#单个资源的银行家算法" class="headerlink" title="单个资源的银行家算法"></a>单个资源的银行家算法</h5><p>一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，算法要做的是判断对请求的满足是否会进入不安全状态，如果是，就拒绝请求；否则予以分配。</p>
<p><img src="/xieyuanhui/2019/07/25/操作系统知识点/img15.jpg" alt></p>
<p>上图 c 为不安全状态，因此算法会拒绝之前的请求，从而避免进入图 c 中的状态。</p>
<p>上图中有五个进程，四个资源。左边的图表示已经分配的资源，右边的图表示还需要分配的资源。最右边的 E、P 以及 A 分别表示：总资源、已分配资源以及可用资源，注意这三个为向量，而不是具体数值，例如 A=(1020)，表示 4 个资源分别还剩下 1/0/2/0。</p>
<p>检查一个状态是否安全的算法如下：</p>
<ul>
<li>查找右边的矩阵是否存在一行小于等于向量 A。如果不存在这样的行，那么系统将会发生死锁，状态是不安全的。</li>
<li>假若找到这样一行，将该进程标记为终止，并将其已分配资源加到 A 中。</li>
<li>重复以上两步，直到所有进程都标记为终止，则状态时安全的。</li>
</ul>
<p>如果一个状态不是安全的，需要拒绝进入这个状态。</p>
<h2 id="内存管理-1"><a href="#内存管理-1" class="headerlink" title="内存管理"></a>内存管理</h2><h3 id="虚拟内存"><a href="#虚拟内存" class="headerlink" title="虚拟内存"></a>虚拟内存</h3><p>虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。</p>
<p>为了更好的管理内存，操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指令。</p>
<p>从上面的描述中可以看出，虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存，也就是说一个程序不需要全部调入内存就可以运行，这使得有限的内存运行大程序成为可能。例如有一台计算机可以产生 16 位地址，那么一个程序的地址空间范围是 0~64K。该计算机只有 32KB 的物理内存，虚拟内存技术允许该计算机运行一个 64K 大小的程序。</p>
<p><img src="/xieyuanhui/2019/07/25/操作系统知识点/img16.jpg" alt></p>
<h3 id="分页系统地址映射"><a href="#分页系统地址映射" class="headerlink" title="分页系统地址映射"></a>分页系统地址映射</h3><p>内存管理单元（MMU）管理着地址空间和物理内存的转换，其中的页表（Page table）存储着页（程序地址空间）和页框（物理内存空间）的映射表。</p>
<p>一个虚拟地址分成两个部分，一部分存储页面号，一部分存储偏移量。</p>
<p>下图的页表存放着 16 个页，这 16 个页需要用 4 个比特位来进行索引定位。例如对于虚拟地址（0010 000000000100），前 4 位是存储页面号 2，读取表项内容为（110 1），页表项最后一位表示是否存在于内存中，1 表示存在。后 12 位存储偏移量。这个页对应的页框的地址为 （110 000000000100）。</p>
<p><img src="/xieyuanhui/2019/07/25/操作系统知识点/img17.jpg" alt></p>
<h3 id="页面置换算法"><a href="#页面置换算法" class="headerlink" title="页面置换算法"></a>页面置换算法</h3><p>在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。</p>
<p>页面置换算法和缓存淘汰策略类似，可以将内存看成磁盘的缓存。在缓存系统中，缓存的大小有限，当有新的缓存到达时，需要淘汰一部分已经存在的缓存，这样才有空间存放新的缓存数据。</p>
<p>页面置换算法的主要目标是使页面置换频率最低（也可以说缺页率最低）。</p>
<h4 id="最佳"><a href="#最佳" class="headerlink" title="最佳"></a>最佳</h4><blockquote>
<p>OPT, Optimal replacement algorithm</p>
</blockquote>
<p>所选择的被换出的页面将是最长时间内不再被访问，通常可以保证获得最低的缺页率。</p>
<p>是一种理论上的算法，因为无法知道一个页面多长时间不再被访问。</p>
<p>举例：一个系统为某进程分配了三个物理块，并有如下页面引用序列：</p>
<p>开始运行时，先将 7, 0, 1 三个页面装入内存。当进程要访问页面 2 时，产生缺页中断，会将页面 7 换出，因为页面 7 再次被访问的时间最长。</p>
<h4 id="最近最久未使用"><a href="#最近最久未使用" class="headerlink" title="最近最久未使用"></a>最近最久未使用</h4><blockquote>
<p>LRU, Least Recently Used</p>
</blockquote>
<p>虽然无法知道将来要使用的页面情况，但是可以知道过去使用页面的情况。LRU 将最近最久未使用的页面换出。</p>
<p>为了实现 LRU，需要在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。</p>
<p>因为每次访问都需要更新链表，因此这种方式实现的 LRU 代价很高。</p>
<p><img src="/xieyuanhui/2019/07/25/操作系统知识点/img18.jpg" alt></p>
<h4 id="最近未使用"><a href="#最近未使用" class="headerlink" title="最近未使用"></a>最近未使用</h4><blockquote>
<p>NRU, Not Recently Used</p>
</blockquote>
<p>每个页面都有两个状态位：R 与 M，当页面被访问时设置页面的 R=1，当页面被修改时设置 M=1。其中 R 位会定时被清零。可以将页面分成以下四类：</p>
<ul>
<li>R=0，M=0</li>
<li>R=0，M=1</li>
<li>R=1，M=0</li>
<li>R=1，M=1</li>
</ul>
<p>当发生缺页中断时，NRU 算法随机地从类编号最小的非空类中挑选一个页面将它换出。</p>
<p>NRU 优先换出已经被修改的脏页面（R=0，M=1），而不是被频繁使用的干净页面（R=1，M=0）。</p>
<h4 id="先进先出"><a href="#先进先出" class="headerlink" title="先进先出"></a>先进先出</h4><blockquote>
<p>FIFO, First In First Out</p>
</blockquote>
<p>选择换出的页面是最先进入的页面。</p>
<p>该算法会将那些经常被访问的页面也被换出，从而使缺页率升高。</p>
<h4 id="第二次机会算法"><a href="#第二次机会算法" class="headerlink" title="第二次机会算法"></a>第二次机会算法</h4><p>FIFO 算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单的修改：</p>
<p>当页面被访问 (读或写) 时设置该页面的 R 位为 1。需要替换的时候，检查最老页面的 R 位。如果 R 位是 0，那么这个页面既老又没有被使用，可以立刻置换掉；如果是 1，就将 R 位清 0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续从链表的头部开始搜索。</p>
<p><img src="/xieyuanhui/2019/07/25/操作系统知识点/img19.jpg" alt></p>
<h4 id="时钟"><a href="#时钟" class="headerlink" title="时钟"></a>时钟</h4><blockquote>
<p>Clock</p>
</blockquote>
<p>第二次机会算法需要在链表中移动页面，降低了效率。时钟算法使用环形链表将页面连接起来，再使用一个指针指向最老的页面。</p>
<p><img src="/xieyuanhui/2019/07/25/操作系统知识点/img20.jpg" alt></p>
<h3 id="分段"><a href="#分段" class="headerlink" title="分段"></a>分段</h3><p>虚拟内存采用的是分页技术，也就是将地址空间划分成固定大小的页，每一页再与内存进行映射。</p>
<p>下图为一个编译器在编译过程中建立的多个表，有 4 个表是动态增长的，如果使用分页系统的一维地址空间，动态增长的特点会导致覆盖问题的出现。</p>
<p><img src="/xieyuanhui/2019/07/25/操作系统知识点/img21.jpg" alt></p>
<p>分段的做法是把每个表分成段，一个段构成一个独立的地址空间。每个段的长度可以不同，并且可以动态增长。</p>
<p><img src="/xieyuanhui/2019/07/25/操作系统知识点/img22.jpg" alt></p>
<h3 id="段页式"><a href="#段页式" class="headerlink" title="段页式"></a>段页式</h3><p>程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。</p>
<h3 id="分页与分段的比较"><a href="#分页与分段的比较" class="headerlink" title="分页与分段的比较"></a>分页与分段的比较</h3><ul>
<li>对程序员的透明性：分页透明，但是分段需要程序员显示划分每个段。</li>
<li>地址空间的维度：分页是一维地址空间，分段是二维的。</li>
<li>大小是否可以改变：页的大小不可变，段的大小可以动态改变。</li>
<li>出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。</li>
</ul>
<h2 id="设备管理-1"><a href="#设备管理-1" class="headerlink" title="设备管理"></a>设备管理</h2><h3 id="磁盘结构"><a href="#磁盘结构" class="headerlink" title="磁盘结构"></a>磁盘结构</h3><ul>
<li>盘面（Platter）：一个磁盘有多个盘面；</li>
<li>磁道（Track）：盘面上的圆形带状区域，一个盘面可以有多个磁道；</li>
<li>扇区（Track Sector）：磁道上的一个弧段，一个磁道可以有多个扇区，它是最小的物理储存单位，目前主要有 512 bytes 与 4 K 两种大小；</li>
<li>磁头（Head）：与盘面非常接近，能够将盘面上的磁场转换为电信号（读），或者将电信号转换为盘面的磁场（写）；</li>
<li>制动手臂（Actuator arm）：用于在磁道之间移动磁头；</li>
<li>主轴（Spindle）：使整个盘面转动。</li>
</ul>
<p><img src="/xieyuanhui/2019/07/25/操作系统知识点/img23.jpg" alt></p>
<h3 id="磁盘调度算法"><a href="#磁盘调度算法" class="headerlink" title="磁盘调度算法"></a>磁盘调度算法</h3><p>读写一个磁盘块的时间的影响因素有：</p>
<ul>
<li>旋转时间（主轴转动盘面，使得磁头移动到适当的扇区上）</li>
<li>寻道时间（制动手臂移动，使得磁头移动到适当的磁道上）</li>
<li>实际的数据传输时间</li>
</ul>
<p>其中，寻道时间最长，因此磁盘调度的主要目标是使磁盘的平均寻道时间最短。</p>
<h4 id="先来先服务"><a href="#先来先服务" class="headerlink" title="先来先服务"></a>先来先服务</h4><blockquote>
<p>FCFS, First Come First Served</p>
</blockquote>
<p>按照磁盘请求的顺序进行调度。</p>
<p>优点是公平和简单。缺点也很明显，因为未对寻道做任何优化，使平均寻道时间可能较长。</p>
<h4 id="最短寻道时间优先"><a href="#最短寻道时间优先" class="headerlink" title="最短寻道时间优先"></a>最短寻道时间优先</h4><blockquote>
<p>SSTF, Shortest Seek Time First</p>
</blockquote>
<p>优先调度与当前磁头所在磁道距离最近的磁道。</p>
<p>虽然平均寻道时间比较低，但是不够公平。如果新到达的磁道请求总是比一个在等待的磁道请求近，那么在等待的磁道请求会一直等待下去，也就是出现饥饿现象。具体来说，两端的磁道请求更容易出现饥饿现象。</p>
<p><img src="/xieyuanhui/2019/07/25/操作系统知识点/img24.jpg" alt></p>
<h4 id="电梯算法"><a href="#电梯算法" class="headerlink" title="电梯算法"></a>电梯算法</h4><blockquote>
<p>SCAN</p>
</blockquote>
<p>电梯总是保持一个方向运行，直到该方向没有请求为止，然后改变运行方向。</p>
<p>电梯算法（扫描算法）和电梯的运行过程类似，总是按一个方向来进行磁盘调度，直到该方向上没有未完成的磁盘请求，然后改变方向。</p>
<p>因为考虑了移动方向，因此所有的磁盘请求都会被满足，解决了 SSTF 的饥饿问题。</p>
<p><img src="/xieyuanhui/2019/07/25/操作系统知识点/img25.jpg" alt></p>
<h2 id="链接"><a href="#链接" class="headerlink" title="链接"></a>链接</h2><h3 id="编译系统"><a href="#编译系统" class="headerlink" title="编译系统"></a>编译系统</h3><p>以下是一个 hello.c 程序：</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;stdio.h&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">   <span class="built_in">printf</span>(<span class="string">"hello, world</span></span><br><span class="line"><span class="string">"</span>);</span><br><span class="line">   <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>在 Unix 系统上，由编译器把源文件转换为目标文件。</p>
<blockquote>
<p>gcc -o hello hello.c</p>
</blockquote>
<p>这个过程大致如下：</p>
<p><img src="/xieyuanhui/2019/07/25/操作系统知识点/img26.jpg" alt></p>
<ul>
<li>预处理阶段：处理以 # 开头的预处理命令；</li>
<li>编译阶段：翻译成汇编文件；</li>
<li>汇编阶段：将汇编文件翻译成可重定向目标文件；</li>
<li>链接阶段：将可重定向目标文件和 printf.o 等单独预编译好的目标文件进行合并，得到最终的可执行目标文件。</li>
</ul>
<h3 id="静态链接"><a href="#静态链接" class="headerlink" title="静态链接"></a>静态链接</h3><p>静态链接器以一组可重定向目标文件为输入，生成一个完全链接的可执行目标文件作为输出。链接器主要完成以下两个任务：</p>
<ul>
<li>符号解析：每个符号对应于一个函数、一个全局变量或一个静态变量，符号解析的目的是将每个符号引用与一个符号定义关联起来。</li>
<li>重定位：链接器通过把每个符号定义与一个内存位置关联起来，然后修改所有对这些符号的引用，使得它们指向这个内存位置。</li>
</ul>
<p><img src="/xieyuanhui/2019/07/25/操作系统知识点/img27.jpg" alt></p>
<h3 id="目标文件"><a href="#目标文件" class="headerlink" title="目标文件"></a>目标文件</h3><ul>
<li>可执行目标文件：可以直接在内存中执行；</li>
<li>可重定向目标文件：可与其它可重定向目标文件在链接阶段合并，创建一个可执行目标文件；</li>
<li>共享目标文件：这是一种特殊的可重定向目标文件，可以在运行时被动态加载进内存并链接； </li>
</ul>
<h3 id="动态链接"><a href="#动态链接" class="headerlink" title="动态链接"></a>动态链接</h3><p>静态库有以下两个问题：</p>
<ul>
<li>当静态库更新时那么整个程序都要重新进行链接；</li>
<li>对于 printf 这种标准函数库，如果每个程序都要有代码，这会极大浪费资源。</li>
</ul>
<p>共享库是为了解决静态库的这两个问题而设计的，在 Linux 系统中通常用 .so 后缀来表示，Windows 系统上它们被称为 DLL。它具有以下特点：</p>
<ul>
<li>在给定的文件系统中一个库只有一个文件，所有引用该库的可执行目标文件都共享这个文件，它不会被复制到引用它的可执行文件中；</li>
<li>在内存中，一个共享库的 .text 节（已编译程序的机器代码）的一个副本可以被不同的正在运行的进程共享。</li>
</ul>
<p><img src="/xieyuanhui/2019/07/25/操作系统知识点/img28.jpg" alt></p>

      
    </div>

    

    
    
    

    
        
<div class="my_post_copyright">
  <script src="//cdn.bootcss.com/clipboard.js/1.5.10/clipboard.min.js"></script>
  
  <!-- JS库 sweetalert 可修改路径 -->
  <script type="text/javascript" src="http://jslibs.wuxubj.cn/sweetalert_mini/jquery-1.7.1.min.js"></script>
  <script src="http://jslibs.wuxubj.cn/sweetalert_mini/sweetalert.min.js"></script>
  <link rel="stylesheet" type="text/css" href="http://jslibs.wuxubj.cn/sweetalert_mini/sweetalert.mini.css">
 
  <p><span>本文标题:</span>操作系统知识点</p>
  <p><span>文章作者:</span>xieyuanhui</p>
  <p><span>发布时间:</span>2019年07月25日 - 16:37:10</p>
  <p><span>最后更新:</span>2019年07月25日 - 21:34:36</p>
  <p><span>原始链接:</span><a href="/xieyuanhui/2019/07/25/操作系统知识点/" title="操作系统知识点">http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/</a>
    <span class="copy-path" title="点击复制文章链接"><i class="fa fa-clipboard" data-clipboard-text="http://xyh5513.gitee.io/xieyuanhui/2019/07/25/操作系统知识点/" aria-label="复制成功！"></i></span>
  </p>
  <p><span>许可协议:</span><i class="fa fa-creative-commons"></i> <a rel="license" href="https://creativecommons.org/licenses/by-nc-nd/4.0/" target="_blank" title="Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)">CC BY-NC-SA 4.0</a> 转载请保留原文链接及作者。</p>  
</div>
<script> 
    var clipboard = new Clipboard('.fa-clipboard');
    clipboard.on('success', $(function(){
      $(".fa-clipboard").click(function(){
        swal({   
          title: "",   
          text: '复制成功',   
          html: false,
          timer: 500,   
          showConfirmButton: false
        });
      });
    }));  
</script>

    

    

    
      
    
    
      <div>
        <div id="reward-container">
  <div>您的支持将鼓励我继续创作</div>
  <button id="reward-button" disable="enable" onclick="var qr = document.getElementById(&quot;qr&quot;); qr.style.display = (qr.style.display === 'none') ? 'block' : 'none';">
    打赏
  </button>
  <div id="qr" style="display: none;">

    
      
      
        
      
      <div style="display: inline-block">
        <img src="/xieyuanhui/images/wechatpay.png" alt="xieyuanhui 微信支付">
        <p>微信支付</p>
      </div>
    
      
      
        
      
      <div style="display: inline-block">
        <img src="/xieyuanhui/images/alipay.jpg" alt="xieyuanhui 支付宝">
        <p>支付宝</p>
      </div>
    

  </div>
</div>

      </div>
    

    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/xieyuanhui/tags/操作系统/" rel="tag"># 操作系统</a>
          
        </div>
      

      
      
        <div class="post-widgets">
        

        

        
          
          <div class="social_share">
            
            
              <div id="needsharebutton-postbottom">
                <span class="btn">
                  <i class="fa fa-share-alt" aria-hidden="true"></i>
                </span>
              </div>
            
            
          </div>
        
        </div>
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/xieyuanhui/2019/07/25/TCP流量控制、拥塞控制/" rel="next" title="TCP流量控制、拥塞控制">
                <i class="fa fa-chevron-left"></i> TCP流量控制、拥塞控制
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/xieyuanhui/2019/07/25/HTTP协议/" rel="prev" title="HTTP协议">
                HTTP协议 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>


  </div>


          </div>
          

  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image" src="/xieyuanhui/images/deer.png" alt="xieyuanhui">
            
              <p class="site-author-name" itemprop="name">xieyuanhui</p>
              <div class="site-description motion-element" itemprop="description"></div>
          </div>

          
            <nav class="site-state motion-element">
              
                <div class="site-state-item site-state-posts">
                
                  <a href="/xieyuanhui/archives/">
                
                    <span class="site-state-item-count">107</span>
                    <span class="site-state-item-name">日志</span>
                  </a>
                </div>
              

              
                
                
                <div class="site-state-item site-state-categories">
                  
                    
                      <a href="/xieyuanhui/categories/">
                    
                  
                    
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                    <span class="site-state-item-count">16</span>
                    <span class="site-state-item-name">分类</span>
                  </a>
                </div>
              

              
                
                
                <div class="site-state-item site-state-tags">
                  
                    
                      <a href="/xieyuanhui/tags/">
                    
                  
                    
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                    <span class="site-state-item-count">114</span>
                    <span class="site-state-item-name">标签</span>
                  </a>
                </div>
              
            </nav>
          

          
            <div class="feed-link motion-element">
              <a href="/xieyuanhui/atom.xml" rel="alternate">
                <i class="fa fa-rss"></i>
                RSS
              </a>
            </div>
          

          

          
            <div class="links-of-author motion-element">
              
                <span class="links-of-author-item">
                  
                  
                    
                  
                  
                    
                  
                  <a href="/xieyuanhui/yuanhxie@163.com" title="E-Mail &rarr; yuanhxie@163.com"><i class="fa fa-fw fa-envelope"></i>E-Mail</a>
                </span>
              
            </div>
          

          

          
          

          
            
          
          

        </div>
      </div>

      
      <!--noindex-->
        <div class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
            
            
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#概述"><span class="nav-text">概述</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#基本特征"><span class="nav-text">基本特征</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#并发"><span class="nav-text">并发</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#共享"><span class="nav-text">共享</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#虚拟"><span class="nav-text">虚拟</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#异步"><span class="nav-text">异步</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#基本功能"><span class="nav-text">基本功能</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#进程管理"><span class="nav-text">进程管理</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#内存管理"><span class="nav-text">内存管理</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#文件管理"><span class="nav-text">文件管理</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#设备管理"><span class="nav-text">设备管理</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#系统调用"><span class="nav-text">系统调用</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#大内核和微内核"><span class="nav-text">大内核和微内核</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#大内核"><span class="nav-text">大内核</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#微内核"><span class="nav-text">微内核</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#中断分类"><span class="nav-text">中断分类</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#外中断"><span class="nav-text">外中断</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#异常"><span class="nav-text">异常</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#陷入"><span class="nav-text">陷入</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#进程管理-1"><span class="nav-text">进程管理</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#进程与线程"><span class="nav-text">进程与线程</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#进程"><span class="nav-text">进程</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#线程"><span class="nav-text">线程</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#区别"><span class="nav-text">区别</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#进程状态切换"><span class="nav-text">进程状态切换</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#进程调度算法"><span class="nav-text">进程调度算法</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#批处理系统"><span class="nav-text">批处理系统</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#先来先服务-first-come-first-serverd（FCFS）"><span class="nav-text">先来先服务 first-come first-serverd（FCFS）</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#短作业优先-shortest-job-first（SJF）"><span class="nav-text">短作业优先 shortest job first（SJF）</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#最短剩余时间优先-shortest-remaining-time-next（SRTN）"><span class="nav-text">最短剩余时间优先 shortest remaining time next（SRTN）</span></a></li></ol></li><li class="nav-item nav-level-4"><a class="nav-link" href="#交互式系统"><span class="nav-text">交互式系统</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#时间片轮转"><span class="nav-text">时间片轮转</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#优先级调度"><span class="nav-text">优先级调度</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#多级反馈队列"><span class="nav-text">多级反馈队列</span></a></li></ol></li><li class="nav-item nav-level-4"><a class="nav-link" href="#实时系统"><span class="nav-text">实时系统</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#进程同步"><span class="nav-text">进程同步</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#临界区"><span class="nav-text">临界区</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#同步与互斥"><span class="nav-text">同步与互斥</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#信号量"><span class="nav-text">信号量</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#管程"><span class="nav-text">管程</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#经典同步问题"><span class="nav-text">经典同步问题</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#读者-写者问题"><span class="nav-text">读者-写者问题</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#哲学家进餐问题"><span class="nav-text">哲学家进餐问题</span></a></li></ol></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#进程通信"><span class="nav-text">进程通信</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#管道"><span class="nav-text">管道</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#FIFO"><span class="nav-text">FIFO</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#消息队列"><span class="nav-text">消息队列</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#信号量-1"><span class="nav-text">信号量</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#存储共享"><span class="nav-text">存储共享</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#套接字"><span class="nav-text">套接字</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#死锁"><span class="nav-text">死锁</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#必要条件"><span class="nav-text">必要条件</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#处理方法"><span class="nav-text">处理方法</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#鸵鸟策略"><span class="nav-text">鸵鸟策略</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#死锁检测与死锁恢复"><span class="nav-text">死锁检测与死锁恢复</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#每种类型一个资源的死锁检测"><span class="nav-text">每种类型一个资源的死锁检测</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#每种类型多个资源的死锁检测"><span class="nav-text">每种类型多个资源的死锁检测</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#死锁恢复"><span class="nav-text">死锁恢复</span></a></li></ol></li><li class="nav-item nav-level-4"><a class="nav-link" href="#死锁预防"><span class="nav-text">死锁预防</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#破坏互斥条件"><span class="nav-text">破坏互斥条件</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#破坏占有和等待条件"><span class="nav-text">破坏占有和等待条件</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#破坏不可抢占条件"><span class="nav-text">破坏不可抢占条件</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#破坏环路等待"><span class="nav-text">破坏环路等待</span></a></li></ol></li><li class="nav-item nav-level-4"><a class="nav-link" href="#死锁避免"><span class="nav-text">死锁避免</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#安全状态"><span class="nav-text">安全状态</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#单个资源的银行家算法"><span class="nav-text">单个资源的银行家算法</span></a></li></ol></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#内存管理-1"><span class="nav-text">内存管理</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#虚拟内存"><span class="nav-text">虚拟内存</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#分页系统地址映射"><span class="nav-text">分页系统地址映射</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#页面置换算法"><span class="nav-text">页面置换算法</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#最佳"><span class="nav-text">最佳</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#最近最久未使用"><span class="nav-text">最近最久未使用</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#最近未使用"><span class="nav-text">最近未使用</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#先进先出"><span class="nav-text">先进先出</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#第二次机会算法"><span class="nav-text">第二次机会算法</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#时钟"><span class="nav-text">时钟</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#分段"><span class="nav-text">分段</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#段页式"><span class="nav-text">段页式</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#分页与分段的比较"><span class="nav-text">分页与分段的比较</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#设备管理-1"><span class="nav-text">设备管理</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#磁盘结构"><span class="nav-text">磁盘结构</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#磁盘调度算法"><span class="nav-text">磁盘调度算法</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#先来先服务"><span class="nav-text">先来先服务</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#最短寻道时间优先"><span class="nav-text">最短寻道时间优先</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#电梯算法"><span class="nav-text">电梯算法</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#链接"><span class="nav-text">链接</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#编译系统"><span class="nav-text">编译系统</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#静态链接"><span class="nav-text">静态链接</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#目标文件"><span class="nav-text">目标文件</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#动态链接"><span class="nav-text">动态链接</span></a></li></ol></li></ol></div>
            

          </div>
        </div>
      <!--/noindex-->
      

      

    </div>
  </aside>
  


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2019</span>
  <span class="with-love" id="animate">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">xieyuanhui</span>

  
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item-icon">
      <i class="fa fa-area-chart"></i>
    </span>
    
      <span class="post-meta-item-text">站点总字数：</span>
    
    <span title="站点总字数">749k</span>
  

  
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item-icon">
      <i class="fa fa-coffee"></i>
    </span>
    
      <span class="post-meta-item-text">站点阅读时长 &asymp;</span>
    
    <span title="站点阅读时长">11:21</span>
  
</div>


  <div class="powered-by">由 <a href="https://hexo.io" class="theme-link" rel="noopener" target="_blank">Hexo</a> 强力驱动 v3.8.0</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 – <a href="https://theme-next.org" class="theme-link" rel="noopener" target="_blank">NexT.Pisces</a> v7.1.0</div>


<div><span id="sitetime"></span>
<script language="javascript">
  function siteTime(){
    window.setTimeout("siteTime()", 1000);
    var seconds = 1000;
    var minutes = seconds * 60;
    var hours = minutes * 60;
    var days = hours * 24;
    var years = days * 365;
    var today = new Date();
    var todayYear = today.getFullYear();
    var todayMonth = today.getMonth()+1;
    var todayDate = today.getDate();
    var todayHour = today.getHours();
    var todayMinute = today.getMinutes();
    var todaySecond = today.getSeconds();
    /* Date.UTC() -- 返回date对象距世界标准时间(UTC)1970年1月1日午夜之间的毫秒数(时间戳)
    year - 作为date对象的年份，为4位年份值
    month - 0-11之间的整数，做为date对象的月份
    day - 1-31之间的整数，做为date对象的天数
    hours - 0(午夜24点)-23之间的整数，做为date对象的小时数
    minutes - 0-59之间的整数，做为date对象的分钟数
    seconds - 0-59之间的整数，做为date对象的秒数
    microseconds - 0-999之间的整数，做为date对象的毫秒数 */
    var t1 = Date.UTC(2019,04,09,15,00,00); //北京时间2018-2-13 00:00:00
    var t2 = Date.UTC(todayYear,todayMonth,todayDate,todayHour,todayMinute,todaySecond);
    var diff = t2-t1;
    var diffYears = Math.floor(diff/years);
    var diffDays = Math.floor((diff/days)-diffYears*365);
    var diffHours = Math.floor((diff-(diffYears*365+diffDays)*days)/hours);
    var diffMinutes = Math.floor((diff-(diffYears*365+diffDays)*days-diffHours*hours)/minutes);
    var diffSeconds = Math.floor((diff-(diffYears*365+diffDays)*days-diffHours*hours-diffMinutes*minutes)/seconds);
    document.getElementById("sitetime").innerHTML=" xieyuanhui的个人笔记已运行"+/*diffYears+" 年 "+*/diffDays+" 天 "+diffHours+" 小时 "+diffMinutes+" 分钟 "+diffSeconds+" 秒";
  }/*因为建站时间还没有一年，就将之注释掉了。需要的可以取消*/
  siteTime();
</script></div>



<div>

  <div class="theme-info">
    <script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
    <span id="busuanzi_container_site_pv">本站总访问量<span id="busuanzi_value_site_pv"></span>次</span>
    <span class="post-meta-divider">|</span>
    <span id="busuanzi_container_site_uv">本站访客数<span id="busuanzi_value_site_uv"></span>人</span>
  </div>

</div>

        






  <div>
    <script type="text/javascript">
	    var cnzz_protocol = (("https:" == document.location.protocol) ? "https://" : "http://");
	    document.write(unescape("%3Cspan id='cnzz_stat_icon_1277235632'%3E%3C/span%3E%3Cscript 
	    src='" + cnzz_protocol + "s23.cnzz.com/z_stat.php%3Fid%3D1277235632%26show%3Dpic' 
	    type='text/javascript'%3E%3C/script%3E"));
    </script>
  </div>



        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    
      <div id="needsharebutton-float">
        <span class="btn">
          <i class="fa fa-share-alt" aria-hidden="true"></i>
        </span>
      </div>
    

    

    
  </div>

  

<script>
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>












  



  
    
    
  
  <script color="0,0,255" opacity="0.5" zindex="-1" count="99" src="/xieyuanhui/lib/canvas-nest/canvas-nest.min.js"></script>













  
  <script src="/xieyuanhui/lib/jquery/index.js?v=2.1.3"></script>

  
  <script src="/xieyuanhui/lib/velocity/velocity.min.js?v=1.2.1"></script>

  
  <script src="/xieyuanhui/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>

  
  <script src="/xieyuanhui/lib/fancybox/source/jquery.fancybox.pack.js"></script>


  


  <script src="/xieyuanhui/js/utils.js?v=7.1.0"></script>

  <script src="/xieyuanhui/js/motion.js?v=7.1.0"></script>



  
  


  <script src="/xieyuanhui/js/affix.js?v=7.1.0"></script>

  <script src="/xieyuanhui/js/schemes/pisces.js?v=7.1.0"></script>



  
  <script src="/xieyuanhui/js/scrollspy.js?v=7.1.0"></script>
<script src="/xieyuanhui/js/post-details.js?v=7.1.0"></script>



  


  <script src="/xieyuanhui/js/next-boot.js?v=7.1.0"></script>


  

  

  

  


  


  
  <script>
    // Popup Window;
    var isfetched = false;
    var isXml = true;
    // Search DB path;
    var search_path = "search.xml";
    if (search_path.length === 0) {
      search_path = "search.xml";
    } else if (/json$/i.test(search_path)) {
      isXml = false;
    }
    var path = "/xieyuanhui/" + search_path;
    // monitor main search box;

    var onPopupClose = function (e) {
      $('.popup').hide();
      $('#local-search-input').val('');
      $('.search-result-list').remove();
      $('#no-result').remove();
      $(".local-search-pop-overlay").remove();
      $('body').css('overflow', '');
    }

    function proceedsearch() {
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay"></div>')
        .css('overflow', 'hidden');
      $('.search-popup-overlay').click(onPopupClose);
      $('.popup').toggle();
      var $localSearchInput = $('#local-search-input');
      $localSearchInput.attr("autocapitalize", "none");
      $localSearchInput.attr("autocorrect", "off");
      $localSearchInput.focus();
    }

    // search function;
    var searchFunc = function(path, search_id, content_id) {
      'use strict';

      // start loading animation
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay">' +
          '<div id="search-loading-icon">' +
          '<i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>' +
          '</div>' +
          '</div>')
        .css('overflow', 'hidden');
      $("#search-loading-icon").css('margin', '20% auto 0 auto').css('text-align', 'center');

      

      $.ajax({
        url: path,
        dataType: isXml ? "xml" : "json",
        async: true,
        success: function(res) {
          // get the contents from search data
          isfetched = true;
          $('.popup').detach().appendTo('.header-inner');
          var datas = isXml ? $("entry", res).map(function() {
            return {
              title: $("title", this).text(),
              content: $("content",this).text(),
              url: $("url" , this).text()
            };
          }).get() : res;
          var input = document.getElementById(search_id);
          var resultContent = document.getElementById(content_id);
          var inputEventFunction = function() {
            var searchText = input.value.trim().toLowerCase();
            var keywords = searchText.split(/[\s\-]+/);
            if (keywords.length > 1) {
              keywords.push(searchText);
            }
            var resultItems = [];
            if (searchText.length > 0) {
              // perform local searching
              datas.forEach(function(data) {
                var isMatch = false;
                var hitCount = 0;
                var searchTextCount = 0;
                var title = data.title.trim();
                var titleInLowerCase = title.toLowerCase();
                var content = data.content.trim().replace(/<[^>]+>/g,"");
                
                var contentInLowerCase = content.toLowerCase();
                var articleUrl = decodeURIComponent(data.url).replace(/\/{2,}/g, '/');
                var indexOfTitle = [];
                var indexOfContent = [];
                // only match articles with not empty titles
                if(title != '') {
                  keywords.forEach(function(keyword) {
                    function getIndexByWord(word, text, caseSensitive) {
                      var wordLen = word.length;
                      if (wordLen === 0) {
                        return [];
                      }
                      var startPosition = 0, position = [], index = [];
                      if (!caseSensitive) {
                        text = text.toLowerCase();
                        word = word.toLowerCase();
                      }
                      while ((position = text.indexOf(word, startPosition)) > -1) {
                        index.push({position: position, word: word});
                        startPosition = position + wordLen;
                      }
                      return index;
                    }

                    indexOfTitle = indexOfTitle.concat(getIndexByWord(keyword, titleInLowerCase, false));
                    indexOfContent = indexOfContent.concat(getIndexByWord(keyword, contentInLowerCase, false));
                  });
                  if (indexOfTitle.length > 0 || indexOfContent.length > 0) {
                    isMatch = true;
                    hitCount = indexOfTitle.length + indexOfContent.length;
                  }
                }

                // show search results

                if (isMatch) {
                  // sort index by position of keyword

                  [indexOfTitle, indexOfContent].forEach(function (index) {
                    index.sort(function (itemLeft, itemRight) {
                      if (itemRight.position !== itemLeft.position) {
                        return itemRight.position - itemLeft.position;
                      } else {
                        return itemLeft.word.length - itemRight.word.length;
                      }
                    });
                  });

                  // merge hits into slices

                  function mergeIntoSlice(text, start, end, index) {
                    var item = index[index.length - 1];
                    var position = item.position;
                    var word = item.word;
                    var hits = [];
                    var searchTextCountInSlice = 0;
                    while (position + word.length <= end && index.length != 0) {
                      if (word === searchText) {
                        searchTextCountInSlice++;
                      }
                      hits.push({position: position, length: word.length});
                      var wordEnd = position + word.length;

                      // move to next position of hit

                      index.pop();
                      while (index.length != 0) {
                        item = index[index.length - 1];
                        position = item.position;
                        word = item.word;
                        if (wordEnd > position) {
                          index.pop();
                        } else {
                          break;
                        }
                      }
                    }
                    searchTextCount += searchTextCountInSlice;
                    return {
                      hits: hits,
                      start: start,
                      end: end,
                      searchTextCount: searchTextCountInSlice
                    };
                  }

                  var slicesOfTitle = [];
                  if (indexOfTitle.length != 0) {
                    slicesOfTitle.push(mergeIntoSlice(title, 0, title.length, indexOfTitle));
                  }

                  var slicesOfContent = [];
                  while (indexOfContent.length != 0) {
                    var item = indexOfContent[indexOfContent.length - 1];
                    var position = item.position;
                    var word = item.word;
                    // cut out 100 characters
                    var start = position - 20;
                    var end = position + 80;
                    if(start < 0){
                      start = 0;
                    }
                    if (end < position + word.length) {
                      end = position + word.length;
                    }
                    if(end > content.length){
                      end = content.length;
                    }
                    slicesOfContent.push(mergeIntoSlice(content, start, end, indexOfContent));
                  }

                  // sort slices in content by search text's count and hits' count

                  slicesOfContent.sort(function (sliceLeft, sliceRight) {
                    if (sliceLeft.searchTextCount !== sliceRight.searchTextCount) {
                      return sliceRight.searchTextCount - sliceLeft.searchTextCount;
                    } else if (sliceLeft.hits.length !== sliceRight.hits.length) {
                      return sliceRight.hits.length - sliceLeft.hits.length;
                    } else {
                      return sliceLeft.start - sliceRight.start;
                    }
                  });

                  // select top N slices in content

                  var upperBound = parseInt('1');
                  if (upperBound >= 0) {
                    slicesOfContent = slicesOfContent.slice(0, upperBound);
                  }

                  // highlight title and content

                  function highlightKeyword(text, slice) {
                    var result = '';
                    var prevEnd = slice.start;
                    slice.hits.forEach(function (hit) {
                      result += text.substring(prevEnd, hit.position);
                      var end = hit.position + hit.length;
                      result += '<b class="search-keyword">' + text.substring(hit.position, end) + '</b>';
                      prevEnd = end;
                    });
                    result += text.substring(prevEnd, slice.end);
                    return result;
                  }

                  var resultItem = '';

                  if (slicesOfTitle.length != 0) {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + highlightKeyword(title, slicesOfTitle[0]) + "</a>";
                  } else {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + title + "</a>";
                  }

                  slicesOfContent.forEach(function (slice) {
                    resultItem += "<a href='" + articleUrl + "'>" +
                      "<p class=\"search-result\">" + highlightKeyword(content, slice) +
                      "...</p>" + "</a>";
                  });

                  resultItem += "</li>";
                  resultItems.push({
                    item: resultItem,
                    searchTextCount: searchTextCount,
                    hitCount: hitCount,
                    id: resultItems.length
                  });
                }
              })
            };
            if (keywords.length === 1 && keywords[0] === "") {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-search fa-5x"></i></div>'
            } else if (resultItems.length === 0) {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-frown-o fa-5x"></i></div>'
            } else {
              resultItems.sort(function (resultLeft, resultRight) {
                if (resultLeft.searchTextCount !== resultRight.searchTextCount) {
                  return resultRight.searchTextCount - resultLeft.searchTextCount;
                } else if (resultLeft.hitCount !== resultRight.hitCount) {
                  return resultRight.hitCount - resultLeft.hitCount;
                } else {
                  return resultRight.id - resultLeft.id;
                }
              });
              var searchResultList = '<ul class=\"search-result-list\">';
              resultItems.forEach(function (result) {
                searchResultList += result.item;
              })
              searchResultList += "</ul>";
              resultContent.innerHTML = searchResultList;
            }
          }

          if ('auto' === 'auto') {
            input.addEventListener('input', inputEventFunction);
          } else {
            $('.search-icon').click(inputEventFunction);
            input.addEventListener('keypress', function (event) {
              if (event.keyCode === 13) {
                inputEventFunction();
              }
            });
          }

          // remove loading animation
          $(".local-search-pop-overlay").remove();
          $('body').css('overflow', '');

          proceedsearch();
        }
      });
    }

    // handle and trigger popup window;
    $('.popup-trigger').click(function(e) {
      e.stopPropagation();
      if (isfetched === false) {
        searchFunc(path, 'local-search-input', 'local-search-result');
      } else {
        proceedsearch();
      };
    });

    $('.popup-btn-close').click(onPopupClose);
    $('.popup').click(function(e){
      e.stopPropagation();
    });
    $(document).on('keyup', function (event) {
      var shouldDismissSearchPopup = event.which === 27 &&
        $('.search-popup').is(':visible');
      if (shouldDismissSearchPopup) {
        onPopupClose();
      }
    });
  </script>





  
  
  <script>
    
    function addCount(Counter) {
      var $visitors = $('.leancloud_visitors');
      var url = $visitors.attr('id').trim();
      var title = $visitors.attr('data-flag-title').trim();

      Counter('get', '/classes/Counter', { where: JSON.stringify({ url }) })
        .done(function({ results }) {
          if (results.length > 0) {
            var counter = results[0];
            
            Counter('put', '/classes/Counter/' + counter.objectId, JSON.stringify({ time: { '__op': 'Increment', 'amount': 1 } }))
            
              .done(function() {
                var $element = $(document.getElementById(url));
                $element.find('.leancloud-visitors-count').text(counter.time + 1);
              })
            
              .fail(function ({ responseJSON }) {
                console.log('Failed to save Visitor num, with error message: ' + responseJSON.error);
              })
          } else {
            
              Counter('post', '/classes/Counter', JSON.stringify({ title: title, url: url, time: 1 }))
                .done(function() {
                  var $element = $(document.getElementById(url));
                  $element.find('.leancloud-visitors-count').text(1);
                })
                .fail(function() {
                  console.log('Failed to create');
                });
            
          }
        })
        .fail(function ({ responseJSON }) {
          console.log('LeanCloud Counter Error: ' + responseJSON.code + ' ' + responseJSON.error);
        });
    }
    

    $(function() {
      $.get('https://app-router.leancloud.cn/2/route?appId=' + 'q2BU0OM2W8i5nARddHRKQOvm-gzGzoHsz')
        .done(function({ api_server }) {
          var Counter = function(method, url, data) {
            return $.ajax({
              method: method,
              url: 'https://' + api_server + '/1.1' + url,
              headers: {
                'X-LC-Id': 'q2BU0OM2W8i5nARddHRKQOvm-gzGzoHsz',
                'X-LC-Key': 'hLTPk12Jmt8atnC9cePjTwQH',
                'Content-Type': 'application/json',
              },
              data: data
            });
          };
          
            addCount(Counter);
          
        });
    });
  </script>



  

  
  

  
  

  
    
      <script type="text/x-mathjax-config">
  

  MathJax.Hub.Config({
    tex2jax: {
      inlineMath: [ ['$', '$'], ['\\(', '\\)'] ],
      processEscapes: true,
      skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
    },
    TeX: {
      
      equationNumbers: {
        autoNumber: 'AMS'
      }
    }
  });
  MathJax.Hub.Register.StartupHook('TeX Jax Ready', function() {
    MathJax.InputJax.TeX.prefilterHooks.Add(function(data) {
      if (data.display) {
        var next = data.script.nextSibling;
        while (next && next.nodeName.toLowerCase() === '#text') { next = next.nextSibling }
        if (next && next.nodeName.toLowerCase() === 'br') { next.parentNode.removeChild(next) }
      }
    });
  });
</script>

<script type="text/x-mathjax-config">
  MathJax.Hub.Queue(function() {
    var all = MathJax.Hub.getAllJax(), i;
    for (i = 0; i < all.length; i += 1) {
      document.getElementById(all[i].inputID + '-Frame').parentNode.className += ' has-jax';
    }
  });
</script>
<script src="//cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML"></script>

    
  


  

  

  

  

  
  
  
  <script src="/xieyuanhui/lib/needsharebutton/needsharebutton.js"></script>
  <script>
    
      pbOptions = {};
      
        pbOptions.iconStyle = "box";
      
        pbOptions.boxForm = "horizontal";
      
        pbOptions.position = "bottomCenter";
      
        pbOptions.networks = "Weibo,Wechat,Douban,QQZone,Twitter,Facebook";
      
      new needShareButton('#needsharebutton-postbottom', pbOptions);
    
    
      flOptions = {};
      
        flOptions.iconStyle = "box";
      
        flOptions.boxForm = "horizontal";
      
        flOptions.position = "middleRight";
      
        flOptions.networks = "Weibo,Wechat,Douban,QQZone,Twitter,Facebook";
      
      new needShareButton('#needsharebutton-float', flOptions);
    
  </script>


  

  

  

  

  

  


  
  <script type="text/javascript" src="//cdn.bootcss.com/canvas-nest.js/1.0.0/canvas-nest.min.js"></script><!-- hexo-inject:begin --><!-- Begin: Injected MathJax -->
<script type="text/x-mathjax-config">
  MathJax.Hub.Config({"tex2jax":{"inlineMath":[["$","$"],["\\(","\\)"]],"skipTags":["script","noscript","style","textarea","pre","code"],"processEscapes":true},"TeX":{"equationNumbers":{"autoNumber":"AMS"}}});
</script>

<script type="text/x-mathjax-config">
  MathJax.Hub.Queue(function() {
    var all = MathJax.Hub.getAllJax(), i;
    for(i=0; i < all.length; i += 1) {
      all[i].SourceElement().parentNode.className += ' has-jax';
    }
  });
</script>

<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js">
</script>
<!-- End: Injected MathJax -->
<!-- hexo-inject:end -->
  
</body>
</html>
